1470A - Strange Birthday Party - CodeForces Solution

binary search dp greedy sortings two pointers *1300

Please click on ads to support us..

Python Code: 

from collections import Counter
tests = int(input())

for test in range(tests):
   n_fre,n_pre= tuple(map(int,input().split(" ")))
   fre_k = list(map(int,input().split(" ")))
   cost = list(map(int,input().split(" ")))
   
   fr_k_cost = []
   for i,k in enumerate(fre_k):
      fr_k_cost.append([cost[k-1],k])

   fr_k_cost.sort(key = lambda x: -x[0])
   dolars = 0
   j = 1
   for pair in fr_k_cost:
      if  j <= pair[1] and  pair[0] > cost[j-1] :
         d = cost[j-1]
         j +=1
      else: d =  pair[0]
      dolars += d
      
   print(dolars)

C++ Code: 

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve(){
    ll n,m;
    cin>>n>>m;
    vector <ll> v1(n);
    vector <ll> v2(m);
    vector <ll> ans(m);
    for(ll i=0;i<n;i++)
    {
        cin>>v1[i]; 
        ans[v1[i]-1]++;
    }
    for(ll i=0;i<m;i++)
    {
        cin>>v2[i];
    }
    ll j=0;
    ll k=m-1;
    ll sum=0;
    for(ll i=0;i<n;i++)
    {
        if(ans[k]==0)
        {
            k--;
            while(1)
            {
                if(ans[k]!=0)
                {
                    break;
                }
                k--;
            }
        }
        if(ans[k]>0)
        {
            if(v2[j]<v2[k])
            {
                sum+=v2[j];
                j++;
            }
            else{
                sum+=v2[k];
            }
            ans[k]--;
        }
    }
    cout<<sum<<endl;
}

int main()                                                                  
{
    ios_base::sync_with_stdio(false);
    ll t = 1;
    cin>>t;
    while(t--)
    {
        solve();
    }   
    return 0;
}


Comments

Submit
0 Comments
More Questions

1602A - Two Subsequences
1555A - PizzaForces
1607B - Odd Grasshopper
1084A - The Fair Nut and Elevator
1440B - Sum of Medians
1032A - Kitchen Utensils
1501B - Napoleon Cake
1584B - Coloring Rectangles
1562B - Scenes From a Memory
1521A - Nastia and Nearly Good Numbers
208. Implement Trie
1605B - Reverse Sort
1607C - Minimum Extraction
1604B - XOR Specia-LIS-t
1606B - Update Files
1598B - Groups
1602B - Divine Array
1594B - Special Numbers
1614A - Divan and a Store
2085. Count Common Words With One Occurrence
2089. Find Target Indices After Sorting Array
2090. K Radius Subarray Averages
2091. Removing Minimum and Maximum From Array
6. Zigzag Conversion
1612B - Special Permutation
1481. Least Number of Unique Integers after K Removals
1035. Uncrossed Lines
328. Odd Even Linked List
1219. Path with Maximum Gold
1268. Search Suggestions System